#include <iostream>
#include <vector>

using namespace std;

class NumArray {
private:
    struct TreeNode {
        int val = 0;
        int begin = 0;
        int end = 0;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
    };
    TreeNode* head;
    int dfs_build(vector<int>& nums, TreeNode*& node, int begin, int end) {
        node = new TreeNode({.begin = begin, .end = end});
        if (begin == end) {
            node->val = nums[begin];
            return nums[begin];
        }
        int mid = (begin + end) / 2;
        node->val += dfs_build(nums, node->left, begin, mid);
        node->val += dfs_build(nums, node->right, mid + 1, end);
        return node->val;
    }
    int dfs_update(TreeNode* node, int& i, int& val) {
        if (node->left != nullptr && node->left->begin <= i && node->left->end >= i) {
            if (node->left->begin == i && node->left->end == i) {
                int sub = val - node->left->val;
                node->left->val = val;
                node->val += sub;
                return sub;
            }
            int _val = dfs_update(node->left, i, val);
            node->val += _val;
            return _val;
        } else if (node->right != nullptr && node->right->begin <= i && node->right->end >= i) {
            if (node->right->begin == i && node->right->end == i) {
                int sub = val - node->right->val;
                node->right->val = val;
                node->val += sub;
                return sub;
            }
            int _val = dfs_update(node->right, i, val);
            node->val += _val;
            return _val;
        }
        return 0;
    }
    int dfs(TreeNode* node, int& begin, int& end) {
        if (node == nullptr) {
            return 0;
        }
        int ans = 0;
        if (node->begin >= begin && node->end <= end) {
            ans += node->val;
            return ans;
        } else if (node->end < begin || node->begin > end) {
            return 0;
        }
        ans += dfs(node->left, begin, end);
        ans += dfs(node->right, begin, end);
        return ans;
    }
public:
    NumArray(vector<int>& nums) {
        if (nums.size() == 0) {
            return;
        }
        dfs_build(nums, head, 0, nums.size() - 1);
    }

    void update(int i, int val) {
        if (head == nullptr) {
            return;
        }
        if (head->begin == i && head->end == i) {
            head->val = val;
            return;
        }
        dfs_update(head, i, val);
    }

    int sumRange(int i, int j) {
        return dfs(head, i, j);
    }
};



int main() {
    vector<int> input = {9, -8};
    NumArray numArray(input);
    numArray.update(0, 3);
    int output = numArray.sumRange(1, 1);
    cout << output << endl;
    numArray.update(1, 2);
    output = numArray.sumRange(0, 2);
    cout << output << endl;
}